// 解题思路：
// 如果 nums1[i] > nums2[i]，则 nums1[i] 相对 nums2[i] 有优势，使 nums1 中的数字对 nusm2 中的数字，优势最大
// 将 nums1 从小到大排序，将 nums2 的下标 index 按照 nums2 从小到大排序
// left = 0, right = n - 1
// index[left] 就表示排完序的 nums2 的第一个元素（最小元素）的原下标
// index[right] 就表示排完序的 nums2 的最后一个元素（最大元素）的原下标
// 贪心策略：排好序后，能比得过就上，比不过就消耗 nums2 里面的上等马
// 如果 nums1[i] > nums2[index[left]]，就把 nums1[i] 放在返回数组的 index[left] 位置，left++
// 如果 nums1[i] <= nums2[index[left]]，就把 nums1[i] 放在返回数组的 index[right] 位置，right--
// 返回结果数组

import java.util.*;

public class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Arrays.sort(nums1);
        Integer[] index = new Integer[n];
        for(int i = 0; i < n; i++) index[i] = i;
        Arrays.sort(index, (a, b) -> nums2[a] - nums2[b]);

        int[] ret = new int[n];
        int left = 0; int right = n - 1;
        for(int x : nums1){
            if(x > nums2[index[left]]){
                ret[index[left++]] = x;
            }else{
                ret[index[right--]] = x;
            }
        }

        return ret;
    }
}
